#pragma once

namespace gyc{

	template<class k>
	struct BSTNode{
		BSTNode(const k& key)
			: _left(nullptr)
			,_right(nullptr)
			,_key(key)
		{

		}

		BSTNode* _left;
		BSTNode* _right;
		k _key;
	};
	

	template<class k>
	class BST {
		typedef BSTNode<k> Node;

	public:
		//BST() = default;
		BST()
		{

		}

		BST(const BST<k>& key)
		{
			Copy(key);
		}

		BST<k>& operator=(BST<k> key)
		{
			swap(_root, key->_root);
			return *this;
		}

		~BST()
		{
			destroy(_root);
			_root = nullptr;
		}

		bool Insert(const k& key)
		{
			if (_root == nullptr)
			{
				_root = new Node(key);
				return true;
			}
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else{
					return false;
				}
			}
			Node* target = new Node(key);
			if (parent->_key < key)
			{
				parent->_right = target;
			}
			else {
				parent->_left = target;
			}
		}
		bool Find(const k& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key < key)
				{
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else {
					return true;
				}
			}
			return false;
		}

		void Erase(const k& key)
		{

			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else {
					//删除
					if (cur->_left == nullptr)
					{
						if (cur == _root)
						{
							cur = cur->_right
						}
						else {
							if (cur == parent->_left)
							{
								parent->_left = cur->_right;
							}
							else {
								parent->_right = cur->_right;
							}
						}
						delete cur;
					}
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							cur = cur->_left;
						}
						else {
							if (cur == parent->_left)
							{
								parent->_left = cur->_left;
							}
							else {
								parent->_right = cur->_left;
							}
						}
						delete cur;
					}
					else {
						Node* pMinright = cur;
						Node* Minright = cur->_left;
						while (Minright->_left)
						{
							pMinright = Minright;
							Minright = Minright->_left;
						}
						swap(cur->_key, Minright->_key);
						if (pMinright->_right == Minright) {
							pMinright->_right = Minright->_right;
						}
						else {
							pMinright->_left = Minright->_right;
						}
						delete cur;
					}
				}
			}
		}

		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}
	private:	
		void _InOrder(Node* _root)
		{
			if (_root == nullptr)
			{
				return;
			}
			_InOrder(_root->_left);
			cout << _root->_key << " ";
			_InOrder(_root->_right);
	    }

		void destroy(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			destroy(root->_left);
			destroy(root->_right);
			delete root;
		}

		Node* Copy(Node* root)
		{
			if (root == nullptr)
			{
				return nullptr
			}
			Node* copy = new Node(root->_key);
			copy->_left = Copy(root->_left);
			copy->_right = Copy(root->_right);

			return copy;
		}

 	private:
		Node* _root = nullptr;
	};






}